/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package arbre;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Xuan Huy
 */
public class ArbreRecherche implements Arbre, Cloneable {

    protected Noeud racine;

    /**
     * Le constructeur par défaut construit un arbre vide.
     */
    public ArbreRecherche() {
    }

    /**
     * Le constructeur construit un arbre en initialisant sa racine.
     *
     * @param racine le noeud racine de l'arbre nouvellement créé.
     */
    public ArbreRecherche(Noeud racine) {
        this.racine = racine;
    }

    /**
     * La méthode retourne une liste de
     * <code>Noeud</code> qui contient toutes les feuilles de l'arbre.
     *
     * @return une liste des feuilles de l'arbre.
     */
    @Override
    public List<Noeud> getFeuilles() {
        return getFeuilles(racine);
    }

    /**
     * La méthode retourne une liste de
     * <code>Noeud</code> qui contient toutes les feuilles de l'arbre enraciné
     * par
     * <code>noeud</code>.
     *
     * @param noeud le noeud racine de l'arbre dont on veut récupérer les
     * noeuds.
     * @return une liste des feuilles de l'arbre.
     */
    public static List<Noeud> getFeuilles(Noeud noeud) {
        List<Noeud> feuilles = new ArrayList<>();
        if (noeud.getGauche() == null && noeud.getDroite() == null) {
            feuilles.add(noeud);
        } else {
            if (noeud.getGauche() != null) {
                feuilles.addAll(getFeuilles(noeud.getGauche()));
            }
            if (noeud.getDroite() != null) {
                feuilles.addAll(getFeuilles(noeud.getDroite()));
            }
        }
        return feuilles;
    }

    /**
     * La méthode retourne la racine de l'arbre.
     *
     * @return la racine de l'arbre, ou <code>null</code> si l'arbre est vide.
     */
    @Override
    public Noeud getRacine() {
        return racine;
    }

    /**
     * La méthode retourne la hauteur de l'arbre, i.e la hauteur de sa racine.
     *
     * @return la hauteur de l'arbre, ou <code>-1</code> si l'arbre est vide.
     */
    @Override
    public int getHauteur() {
        if (racine == null) {
            return -1;
        }
        return racine.getHauteur();
    }

    /**
     * La méthode change la racine de l'arbre, en écrasant l'ancienne.
     *
     * @param racine le nouveau noeud racine.
     */
    public void setRacine(Noeud racine) {
        this.racine = racine;
    }

    /**
     * La méthode réalise un parcours infixe de l'arbre enraciné par
     * <code>noeud</code>.
     *
     * @param noeud le noeud racine de l'arbre à parcourir.
     * @return une liste de <code>Noeud</code> représentant le parcours infixe.
     */
    public static List<Noeud> parcoursInfixe(Noeud noeud) {
        List<Noeud> noeuds = new ArrayList<>();
        if (noeud != null) {
            noeuds.addAll(parcoursInfixe(noeud.getGauche()));
            noeuds.add(noeud);
            noeuds.addAll(parcoursInfixe(noeud.getDroite()));
        }
        return noeuds;
    }

    /**
     * La méthode réalise un parcours infixe de l'arbre actuel.
     *
     * @return une liste de <code>Noeud</code> représentant le parcours infixe.
     */
    public List<Noeud> parcoursInfixe() {
        return parcoursInfixe(racine);
    }

    /**
     * La méthode recherche le noeud dont la clé vaut
     * <code>cle</code> dans l'arbre enraciné par
     * <code>noeud</code>.
     *
     * @param noeud le noeud racine de l'arbre.
     * @param cle la valeur de la clé recherchée.
     * @return le noeud de l'arbre dont la valeur de la clé
     * vaut <code>cle</code>.
     */
    public static Noeud rechercher(Noeud noeud, int cle) {
        if (noeud == null || noeud.getCle() == cle) {
            return noeud;
        }
        if (cle < noeud.getCle()) {
            return rechercher(noeud.getGauche(), cle);
        } else {
            return rechercher(noeud.getDroite(), cle);
        }
    }

    /**
     * La méthode recherche le noeud dont la clé vaut
     * <code>cle</code> dans l'arbre actuel.
     *
     * @param cle la valeur de la clé recherchée.
     * @return le noeud de l'arbre dont la valeur de la clé
     * vaut <code>cle</code>.
     */
    @Override
    public Noeud rechercher(int cle) {
        return rechercher(racine, cle);
    }

    /**
     * La méthode recherche le noeud dont la clé est minimale dans l'arbre
     * enraciné par
     * <code>noeud</code>.
     *
     * @param noeud le noeud racine de l'arbre sur lequel est effectuée la
     * recherche.
     * @return le noeud dont la valeur de la clé est minimale.
     */
    public static Noeud minimum(Noeud noeud) {
        Noeud noeudIntermediaire = noeud;
        while (noeudIntermediaire.getGauche() != null) {
            noeudIntermediaire = noeudIntermediaire.getGauche();
        }
        return noeudIntermediaire;
    }

    /**
     * La méthode recherche le noeud dont la clé est minimale dans l'arbre
     * actuel.
     *
     * @return le noeud dont la valeur de la clé est minimale.
     */
    @Override
    public Noeud minimum() {
        return minimum(racine);
    }

    /**
     * La méthode recherche le noeud dont la clé est maximale dans l'arbre
     * enraciné par
     * <code>noeud</code>.
     *
     * @param noeud noeud le noeud racine de l'arbre sur lequel est effectuée la
     * recherche.
     * @return le noeud dont la valeur de la clé est maximale.
     */
    public static Noeud maximum(Noeud noeud) {
        Noeud noeudIntermediaire = noeud;
        while (noeudIntermediaire.getDroite() != null) {
            noeudIntermediaire = noeudIntermediaire.getDroite();
        }
        return noeudIntermediaire;
    }

    /**
     * La méthode recherche le noeud dont la clé est maximale dans l'arbre
     * actuel.
     *
     * @return le noeud dont la valeur de la clé est maximale.
     */
    @Override
    public Noeud maximum() {
        return maximum(racine);
    }

    /**
     * La méthode recherche le noeud successeur de
     * <code>noeud</code>, i.e le noeud dont la clé est immédiatement supérieure
     * à celle de
     * <code>noeud</code>. C'est aussi le successeur de
     * <code>noeud</code> dans l'ordre déterminé par un parcours infixe.
     *
     * @param noeud le noeud dont on veut trouver le successeur.
     * @return le noeud successeur de <code>noeud</code>, ou <code>null</code>
     * si la clé de <code>noeud</noeud> est la plus grande.
     */
    public static Noeud successeur(Noeud noeud) {
        if (noeud.getDroite() != null) {
            return minimum(noeud.getDroite());
        }
        /**
         * On considère le cas où noeud n'a pas d'enfant droite.
         */
        Noeud parent = noeud.getParent();
        while (parent != null && noeud == parent.getDroite()) {
            noeud = parent;
            parent = parent.getParent();
        }
        return parent;
    }

    /**
     * La méthode recherche le noeud prédécesseur de
     * <code>noeud</code>, i.e le noeud dont la clé est immédiatement inférieure
     * à celle de
     * <code>noeud</code>. C'est aussi le prédécesseur de
     * <code>noeud</code> dans l'ordre déterminé par un parcours infixe.
     *
     * @param noeud le noeud dont on veut trouver le prédécesseur.
     * @return le noeud prédécesseur de <code>noeud</code>, ou <code>null</code>
     * si la clé de <code>noeud</noeud> est la plus petite.
     */
    public static Noeud predecesseur(Noeud noeud) {
        if (noeud.getGauche() != null) {
            return maximum(noeud.getGauche());
        }
        /**
         * On considère le cas où noeud n'a pas d'enfant gauche.
         */
        Noeud parent = noeud.getParent();
        while (parent != null && noeud == parent.getGauche()) {
            noeud = parent;
            parent = parent.getParent();
        }
        return parent;
    }

    /**
     * La méthode insère le noeud
     * <code>noeud</code> dans l'arbre actuel, tout en conservant les
     * contraintes d'un arbre binaire de recherche.
     *
     * @param noeud le nouveau noeud à insérer dans l'arbre.
     */
    @Override
    public void inserer(Noeud noeud) {
        Noeud y = null;
        Noeud x = racine;
        while (x != null) {
            y = x;
            if (noeud.getCle() < x.getCle()) {
                x = x.getGauche();
            } else {
                x = x.getDroite();
            }
        }
        noeud.setParent(y);
        if (y == null) {
            /**
             * Si l'arbre est vide, on initialise tout simplement sa racine par
             * le nouveau noeud.
             */
            racine = noeud;
        } else if (noeud.getCle() < y.getCle()) {
            y.setGauche(noeud);
        } else {
            y.setDroite(noeud);
        }
    }

    /**
     * La méthode supprime le noeud
     * <code>noeud</code> de l'arbre actuel, tout en conservant les contraintes
     * d'un arbre binaire de recherche.
     *
     * @param noeud le noeud à supprimer.
     * @return le noeud détaché suite à la suppression.
     */
    @Override
    public Noeud supprimer(Noeud noeud) {
        Noeud x, noeudDetache;
        if (noeud.getGauche() == null || noeud.getDroite() == null) {
            noeudDetache = noeud;
        } else {
            noeudDetache = successeur(noeud);
        }
        if (noeudDetache.getGauche() != null) {
            x = noeudDetache.getGauche();
        } else {
            x = noeudDetache.getDroite();
        }
        if (x != null) {
            x.setParent(noeudDetache.getParent());
        }
        if (noeudDetache.getParent() == null) {
            racine = x;
        } else if (noeudDetache == noeudDetache.getParent().getGauche()) {
            noeudDetache.getParent().setGauche(x);
        } else {
            noeudDetache.getParent().setDroite(x);
        }
        if (noeudDetache != noeud) {
            noeud.setCle(noeudDetache.getCle());
        }
        return noeudDetache;
    }

    /**
     * La méthode retourne une copie de l'arbre actuel en recopiant le noeud
     * <code>racine</code>.
     *
     * @return une copie de cet arbre.
     */
    @Override
    public Object clone() {
        ArbreRecherche copy = null;
        try {
            copy = (ArbreRecherche) super.clone();
            if (racine != null) {
                copy.racine = (Noeud) racine.clone();
            }
        } catch (CloneNotSupportedException ex) {
            ex.printStackTrace();
        }
        return copy;
    }
}
